{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Semi-Ordered Permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: semiOrderedPermutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #半有序排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的整数排列 <code>nums</code> 。</p>\n",
    "\n",
    "<p>如果排列的第一个数字等于 <code>1</code> 且最后一个数字等于 <code>n</code> ，则称其为 <strong>半有序排列</strong> 。你可以执行多次下述操作，直到将 <code>nums</code> 变成一个 <strong>半有序排列</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择 <code>nums</code> 中相邻的两个元素，然后交换它们。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回使 <code>nums</code> 变成 <strong>半有序排列</strong> 所需的最小操作次数。</p>\n",
    "\n",
    "<p><strong>排列</strong> 是一个长度为 <code>n</code> 的整数序列，其中包含从 <code>1</code> 到 <code>n</code> 的每个数字恰好一次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,1,4,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>可以依次执行下述操作得到半有序排列：\n",
    "1 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。\n",
    "2 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。\n",
    "可以证明，要让 nums 成为半有序排列，不存在执行操作少于 2 次的方案。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,4,1,3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：\n",
    "</strong>可以依次执行下述操作得到半有序排列：\n",
    "1 - 交换下标 1 和下标 2 对应元素。排列变为 [2,1,4,3] 。\n",
    "2 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。\n",
    "3 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。\n",
    "可以证明，要让 nums 成为半有序排列，不存在执行操作少于 3 次的方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,3,4,2,5]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>这个排列已经是一个半有序排列，无需执行任何操作。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length == n &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= nums[i]&nbsp;&lt;= 50</code></li>\n",
    "\t<li><code>nums</code> 是一个 <strong>排列</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [semi-ordered-permutation](https://leetcode.cn/problems/semi-ordered-permutation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [semi-ordered-permutation](https://leetcode.cn/problems/semi-ordered-permutation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,4,3]', '[2,4,1,3]', '[1,3,4,2,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = nums.index(1)\n",
    "        j = nums.index(n)\n",
    "        return i - j + n - 1 - int(i > j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        a = nums.index(1)\n",
    "        b = nums.index(len(nums))\n",
    "        if b < a:\n",
    "            return a + len(nums) - b -2\n",
    "        else:\n",
    "            return a + len(nums) - b - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = nums.index(1)\n",
    "        q = nums.index(n)\n",
    "        return p + n - 1 - q - (p > q)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = nums.index(1)\n",
    "        j = nums.index(n)\n",
    "        return i+n-1-j-(i>j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = nums.index(1)\n",
    "        j = nums.index(n)\n",
    "        if i < j:\n",
    "            return n-1+i-j\n",
    "        return n-2+i-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        idx1,idxn = nums.index(1),nums.index(n)\n",
    "        if idx1 > idxn:\n",
    "            return idx1 + n - 1 - idxn - 1\n",
    "        return idx1 + n - 1 - idxn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = nums.index(1)\n",
    "        q = nums.index(n)\n",
    "        return p + n - 1 - q - (p > q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        m = nums.index(max(nums))\n",
    "        n = nums.index(min(nums))\n",
    "        return len(nums)-1-m+n if m>n else len(nums)-2-m+n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        if nums.index(1) > nums.index(len(nums)):\n",
    "            count_sum = nums.index(1) + len(nums) - nums.index(len(nums)) - 1 - 1\n",
    "        else:\n",
    "            count_sum = nums.index(1) + len(nums) - nums.index(len(nums)) - 1\n",
    "        return count_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        numsDict = dict()\n",
    "        for i in range(0, len(nums)):\n",
    "            numsDict[nums[i]] = i\n",
    "        judge = numsDict.get(1) -  numsDict.get(len(nums))\n",
    "        if judge > 0:\n",
    "            return len(nums) + judge - 2\n",
    "        else:\n",
    "            return len(nums) + judge - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        first, last = inf, 0\n",
    "        f, l = 51, 0\n",
    "        for i in range(n):\n",
    "            if nums[i] > last:\n",
    "                last = nums[i]\n",
    "                l = i\n",
    "            if nums[i] < first:\n",
    "                first = nums[i]\n",
    "                f = i\n",
    "\n",
    "        if f > l:\n",
    "            return f + n - l - 2\n",
    "        else:\n",
    "            return n + f - l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        first, last = inf, 0\n",
    "        f, l = 51, 0\n",
    "        for i in range(n):\n",
    "            if nums[i] > last:\n",
    "                last = nums[i]\n",
    "                l = i\n",
    "            if nums[i] < first:\n",
    "                first = nums[i]\n",
    "                f = i\n",
    "\n",
    "        if f > l:\n",
    "            return f + n - l - 2\n",
    "        else:\n",
    "            return n + f - l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = 0\n",
    "        m = nums.index(min(nums))\n",
    "        while m > 0:\n",
    "            nums[m], nums[m - 1] = nums[m - 1], nums[m]\n",
    "            m -= 1\n",
    "            n += 1\n",
    "        j = nums.index(max(nums))\n",
    "        while j < len(nums)-1:\n",
    "            nums[j], nums[j + 1] = nums[j + 1], nums[j]\n",
    "            j += 1\n",
    "            n += 1\n",
    "        if nums[0] == 1 and nums[-1] == len(nums):\n",
    "            return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if 1 and n not in nums:\n",
    "            return False\n",
    "        i,j = nums.index(1),nums.index(n)\n",
    "        if i < j:return n - j - 1 + i\n",
    "        if i > j:return n - j + i -2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        m = max(nums) \n",
    "        index_m = nums.index(m) \n",
    "        # 1 一定是是存在的\n",
    "        index_1 = nums.index(1)\n",
    "        # 两种情况，一种是1，m位置不交错，第二种就是位置交错\n",
    "        if index_m < index_1 :\n",
    "            return index_1 + len(nums) - 1 - index_m -1  \n",
    "        else :\n",
    "            return index_1 + len(nums) -1 - index_m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]==1:\n",
    "                l = i \n",
    "            if nums[i]==n:\n",
    "                r = i \n",
    "        if l < r:\n",
    "              return l + n - 1 - r \n",
    "        else:\n",
    "            return l + n - 1 - r - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        maxNumber = len(nums)\n",
    "        moveOne = list(range(0,nums.index(1)+1))\n",
    "        movemaxNumber = list(range(nums.index(len(nums)),maxNumber))\n",
    "        # 确定有没有交集\n",
    "        setMoveOne = set(moveOne)\n",
    "        setMoveMax = set(movemaxNumber)\n",
    "        if len(setMoveOne & setMoveMax)==0:\n",
    "            return (len(setMoveOne)-1)+(len(setMoveMax)-1)\n",
    "        else:\n",
    "            return (len(setMoveOne) - 1) + (len(setMoveMax) - 1)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        minindex = -1\n",
    "        maxindex = -1\n",
    "        mini = 51\n",
    "        maxi = 0\n",
    "        lenn = len(nums)-1\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            if num < mini:\n",
    "                mini = num\n",
    "                minindex = i\n",
    "            if num > maxi:\n",
    "                maxi = num\n",
    "                maxindex = i\n",
    "        \n",
    "        if minindex < maxindex:\n",
    "            return minindex + lenn - maxindex\n",
    "        else:\n",
    "            return minindex + lenn - maxindex - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        if nums.index(min(nums)) > nums.index(max(nums)): \n",
    "            return nums.index(min(nums)) + len(nums) - nums.index(max(nums)) - 2\n",
    "        return nums.index(min(nums)) + len(nums) - nums.index(max(nums)) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        id_1, id_n = nums.index(1), nums.index(n := len(nums))\n",
    "        return id_1 + n - id_n - 1 - (id_1 > id_n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int: \n",
    "        # if nums.index(1) > nums.index(len(nums)):\n",
    "        #     return nums.index(1) + (len(nums)-nums.index(len(nums))-1) - 1 \n",
    "        # else:\n",
    "        #     return nums.index(1) + (len(nums)-nums.index(len(nums))-1)\n",
    "        n = len(nums)\n",
    "        p = nums.index(1)\n",
    "        q = nums.index(n)\n",
    "        return p + n - 1 - q - (p > q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        idx1=nums.index(1)\n",
    "        idxn=nums.index(n)\n",
    "        if idx1<idxn:\n",
    "            return idx1+n-1-idxn\n",
    "        return idx1+n-1-idxn-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f_index = nums.index(1)\n",
    "        e_index = nums.index(n)\n",
    "        if(f_index > e_index):\n",
    "            return f_index + n - e_index - 2\n",
    "        else:\n",
    "            return n - e_index + f_index - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        if nums[0]==1 and nums[-1]==len(nums):\n",
    "            return 0\n",
    "        elif nums.index(1)<nums.index(len(nums)):\n",
    "            return nums.index(1)+len(nums)-nums.index(len(nums))-1\n",
    "        else:\n",
    "            return nums.index(1)+len(nums)-nums.index(len(nums))-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        idx1 = nums.index(1)\n",
    "        idx2 = nums.index(n)\n",
    "        if idx1 < idx2:\n",
    "            return idx1 + n-1 -idx2\n",
    "        return idx1 + n-2- idx2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l = nums.index(1)\n",
    "        r = nums.index(n)\n",
    "        ans = l + n - r - 1\n",
    "        if l > r:\n",
    "            ans -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            # 找等于 1 的数，和等于 n 的数\n",
    "            if nums[i] == 1:\n",
    "                left = i\n",
    "            if nums[i] == n:\n",
    "                right = i\n",
    "        if left < right:\n",
    "            return left + n - right - 1\n",
    "        else:\n",
    "            return left+n-right-1-1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = nums.index(1)\n",
    "        q = nums.index(n)\n",
    "        return p + n - 1 - q - (p > q)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if nums[0] == 1 and nums[-1] == n:\n",
    "            return 0\n",
    "        f_index = nums.index(1)\n",
    "        e_index = nums.index(n)\n",
    "        if(f_index > e_index):\n",
    "            return f_index + n - e_index - 2\n",
    "        else:\n",
    "            return n - e_index + f_index - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        idx1=nums.index(1)\n",
    "        idxn=nums.index(n)\n",
    "        if idxn>idx1:\n",
    "            ans=idx1+n-idxn-1\n",
    "\n",
    "        else:\n",
    "            ans=idx1+n-idxn-1-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        p=nums.index(min(nums))\n",
    "        q=nums.index(max(nums))\n",
    "        inc = 1 if p>q else 0 \n",
    "        return p+n-q-1-inc\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        numsDict = dict()\n",
    "        numslen = len(nums)\n",
    "        for i in range(0, numslen):\n",
    "            numsDict[nums[i]] = i\n",
    "        judge = numsDict.get(1) -  numsDict.get(numslen)\n",
    "        if judge > 0:\n",
    "            return numslen + judge - 2\n",
    "        else:\n",
    "            return numslen + judge - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        i = nums.index(1)\n",
    "        for j in range(i-1, -1, -1):\n",
    "            nums[j], nums[j+1] = nums[j+1], nums[j]\n",
    "            ans += 1\n",
    "            \n",
    "        i = nums.index(n)\n",
    "        for j in range(i, n-1):\n",
    "            nums[j], nums[j + 1] = nums[j + 1], nums[j]\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "#         n=len(nums)\n",
    "#         x=nums.index(1)\n",
    "#         y=nums.index(n)\n",
    "#         return x+n-1-y if x<y else x+n-1-y-1\n",
    "\n",
    "### 灵茶山\n",
    "class Solution:\n",
    "\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        p = nums.index(1)\n",
    "\n",
    "        q = nums.index(n)\n",
    "\n",
    "        return p + n - 1 - q - (p > q) ###判断优雅\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        return nums.index(1) + (len(nums)-nums.index(len(nums))-1) if nums.index(1)<nums.index(len(nums)) else nums.index(1) + (len(nums)-nums.index(len(nums))-1) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        a,b=nums.index(1),nums.index(len(nums))\n",
    "        return a+len(nums)-1-b+(-1 if b<a else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        idx_1 = nums.index(1)\n",
    "        idx_n = nums.index(n)\n",
    "\n",
    "        if idx_1 > idx_n:\n",
    "            ans = idx_1 + n - 1 - idx_n - 1\n",
    "        else:\n",
    "            ans = idx_1 + n - 1 - idx_n\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if nums[0] == 1 and nums[n-1] == n:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                l = i\n",
    "            if nums[i] == n:\n",
    "                r = i\n",
    "        if l < r:\n",
    "            return l + (n - 1 - r)\n",
    "        else:\n",
    "            return l + (n - 1 - r) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        idx1 , idx2 = 0 , 0\n",
    "        for i , num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                idx1 = i\n",
    "            if num == len(nums):\n",
    "                idx2 = i\n",
    "        res = idx1 + len(nums) - 1 - idx2\n",
    "        if idx1 > idx2:\n",
    "            res -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = nums.index(1)\n",
    "        q = nums.index(n)\n",
    "        return p + n - 1 - q - (p > q)\n",
    "        \n",
    "        # ans = [-1, -1]\n",
    "        # n = len(nums)\n",
    "        # for idx,num in enumerate(nums):\n",
    "        #     if num == 1:\n",
    "        #         ans[0] = idx\n",
    "        #     elif num == n:\n",
    "        #         ans[1] = idx\n",
    "        # if ans[0] < ans[1]:\n",
    "        #     return ans[0] + n - 1 - ans[1]\n",
    "        # else:\n",
    "        #     return ans[0] + n - 2 - ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        return i + n - 1 - j if (i := nums.index(1)) < (j := nums.index(n := len(nums))) else i + n - 2 - j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = nums.index(1)\n",
    "        q = nums.index(n)\n",
    "        return p + n - 1 - q - (p > q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def find(t):\n",
    "            for i,x in enumerate(nums):\n",
    "                if x ==t:\n",
    "                    return i\n",
    "        i = find(1)\n",
    "        j = find(n)\n",
    "\n",
    "        if i <j :\n",
    "            return i+n-j-1\n",
    "        else: return i+n-j-2\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        x=nums.index(1)\n",
    "        y=nums.index(len(nums))\n",
    "        if x<y:\n",
    "            return x+len(nums)-1-y\n",
    "        else:\n",
    "            return x+len(nums)-2-y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if nums.index(1)<nums.index(n):\n",
    "            return nums.index(1)+(n-1-nums.index(n))\n",
    "        return nums.index(1)+(n-1-nums.index(n))-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a1 = nums.index(1)\n",
    "        a2 = nums.index(n)\n",
    "        return a1 + n - a2 - 1 if a1 < a2 else a1 + n - a2 - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a,b = nums.index(min(nums)),nums.index(max(nums))\n",
    "        if a<b:\n",
    "            return a+n-b-1\n",
    "        else:\n",
    "            return a+n-b-1-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        i1=nums.index(1)\n",
    "        i2=nums.index(n)\n",
    "\n",
    "        return i1+n-i2-1 if i1<i2 else i1+n-i2-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        i, j = 0, 0\n",
    "        for index in range(len(nums)):\n",
    "            if nums[index] == min(nums):\n",
    "                i = index\n",
    "            if nums[index] == max(nums):\n",
    "                j = index\n",
    "        if i < j:\n",
    "            return i + (len(nums) - j - 1)\n",
    "        else:\n",
    "            return i + (len(nums) - j - 1) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        one_index=0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                one_index=i\n",
    "                break\n",
    "        ans=0\n",
    "        ans+=one_index\n",
    "        nums.pop(one_index)\n",
    "        # print(nums)\n",
    "        nums.insert(0,1)\n",
    "        # print(nums)\n",
    "        n_index=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]==n:\n",
    "                n_index=i\n",
    "                break\n",
    "        ans+=n-1-n_index\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = nums.index(1)\n",
    "        q = nums.index(n)\n",
    "        return p + n - 1 - q - (p > q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        minind = nums.index(min(nums))\n",
    "        maxind = nums.index(max(nums))\n",
    "        result = len(nums) - maxind - 1 + minind\n",
    "        if minind > maxind:\n",
    "            result -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        numsDict = dict()\n",
    "        for i in range(0, len(nums)):\n",
    "            numsDict[nums[i]] = i\n",
    "        if numsDict.get(len(nums)) < numsDict.get(1):\n",
    "            return len(nums) -  numsDict.get(len(nums)) + numsDict.get(1) - 2\n",
    "        else:\n",
    "            return len(nums) -  numsDict.get(len(nums)) + numsDict.get(1) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        idx_1 = nums.index(1) \n",
    "        idx_n = nums.index(n) \n",
    "        if idx_1 < idx_n :\n",
    "            return idx_1 + (n - 1) - idx_n\n",
    "        elif idx_1 > idx_n:\n",
    "            return idx_1 + (n - 1) - idx_n - 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        Idx1 = nums.index(1)\n",
    "        Idxn = nums.index(n)\n",
    "        return Idx1 + (n - Idxn - 1) if Idx1 < Idxn else Idx1 + (n - Idxn - 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        ans = nums.index(1)\n",
    "        nums = [1] + nums[:ans] + nums[ans+1:]\n",
    "        return ans + len(nums) - 1 - nums.index(len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        a=max(nums)\n",
    "        b=min(nums)\n",
    "        d=nums.index(a)\n",
    "        c=nums.index(b)\n",
    "        if d<c:\n",
    "            ans=c+len(nums)-d-2\n",
    "        else:\n",
    "            ans=c+len(nums)-d-1\n",
    "        return(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        a,b=nums.index(1),nums.index(len(nums))\n",
    "        return a+len(nums)-1-b+(-1 if b<a else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        idx1 = nums.index(1)\n",
    "        idx2 = nums.index(n)\n",
    "        if idx1 < idx2:\n",
    "            return idx1 + n-1-idx2\n",
    "        return idx1 + n-2-idx2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         for i in range(n):\n",
    "#             # 找等于 1 的数，和等于 n 的数\n",
    "#             if nums[i] == 1:\n",
    "#                 left = i\n",
    "#             if nums[i] == n:\n",
    "#                 right = i\n",
    "#         if left < right:\n",
    "#             return left + n - right - 1\n",
    "#         el\n",
    "#             return left+n-right-1-1\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left=right=0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                left = i\n",
    "            if nums[i] == n:\n",
    "                right = i\n",
    "        res = 0\n",
    "        # 交换次数，其实1 距离左边几个值，就交换几次，但分情况，就是 n 在 1 前面，和 n在 1 后面的情况。\n",
    "        # n如果在 1 前面，那在 1 交换的过程中，n 的位置就会变化\n",
    "        if left <right:\n",
    "            # 1在 n 的前面，就是 left+(n-1)-right\n",
    "            res = left + (n - 1 - right)\n",
    "        else:\n",
    "            # 1在 n 的皇后，right索引等于变成了 right+1，所以 left+[(n-1)-(right+1)]\n",
    "            res = left + (n - 1 - (right + 1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        min_v = inf \n",
    "        max_v = -inf\n",
    "        min_index = max_index = -1\n",
    "        for index , num in enumerate(nums):\n",
    "            if num > max_v:\n",
    "                max_v = num\n",
    "                max_index = index\n",
    "            if num < min_v:\n",
    "                min_v = num\n",
    "                min_index = index\n",
    "        if min_index == 0 and max_index==len(nums)-1:\n",
    "            return 0\n",
    "        if max_index<min_index:\n",
    "            return  min_index+ len(nums)-1-max_index-1\n",
    "        return  min_index+ len(nums)-1-max_index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        i0 = nums.index(1)\n",
    "        i1 = nums.index(len(nums))\n",
    "        return i0 + len(nums) - 1 - i1 if i0 <= i1 else i0 + len(nums) - 2 - i1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        if nums[0] == 1 and nums[-1] == max(nums):\n",
    "            return 0\n",
    "        idx_1, idx_max = nums.index(1), nums.index(max(nums))\n",
    "        if idx_1 < idx_max:\n",
    "            return idx_1 + len(nums) - 1 - idx_max\n",
    "        else:\n",
    "            return idx_1 + len(nums) - 1 - idx_max - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def semiOrderedPermutation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = nums.index(1)\n",
    "        q = nums.index(n)\n",
    "        return p + n - 1 - q - (p > q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def semiOrderedPermutation(self, nums) -> int:\r\n",
    "        indexFirst = nums.index(1)\r\n",
    "        indexEnd = nums.index(len(nums))\r\n",
    "\r\n",
    "        if indexFirst < indexEnd:\r\n",
    "            return indexFirst + len(nums) - 1 - indexEnd\r\n",
    "        else:\r\n",
    "            return indexFirst + len(nums) - 2 - indexEnd\r\n",
    "\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
